#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 020. 有效的括号.py
@time: 2022/2/20 19:27
@desc: https://leetcode-cn.com/problems/valid-parentheses/
> 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
    1. 左括号必须用相同类型的右括号闭合。
    2. 左括号必须以正确的顺序闭合。

1. 栈
2. t: O(n), s: O(n)

'''
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if len(s)<2: return False
        stack = []
        for t in s:
            if t in ['(', '{', '[']:
                stack.append(t)
            elif t==']':
                if not stack or not stack.pop()=='[': return False
            elif t=='}':
                if not stack or not stack.pop()=='{': return False
            elif t==')':
                if not stack or not stack.pop()=='(': return False
            else:
                return False
        return len(stack)==0